4.1.9.4 希尔排序 （不稳定排序）
- 时间复杂度： O（n）（根据步长序列的不同而不同）
- 空间复杂度： O（n）
思想：优先比较距离较远的元素，核心在于间隔序列的设定
var arr = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04];
var len = arr.length;
for (var fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {
for (var i = fraction; i < len; i++) {
for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {
var temp = arr[j];
arr[j] = arr[fraction + j];
arr[fraction + j] = temp;
}
}
}
console.log(arr);
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
- demo
[13,14,93,33,82,25,94,65,23]
设置步长 5
比较 13 和 25 ，13 < 25 不换位置
比较 14 和 94， 14 < 65 不换位置
比较 93 和 23 ， 93 > 23 换位置
比较 82
这时候第一次后： 13 14 65 23 82 25 94 93 33
再设置步长为 3
比较 13 和 23
比较 14 和 82
65 和 25
....
再设置步长为 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22